PGP sử dụng kết hợp mật mã hóa khóa công khai và thuật toán khóa đối xứng cộng thêm với hệ thống xác lập mối quan hệ giữa khóa công khai và chỉ danh người dùng (ID). Phiên bản đầu tiên của hệ thống này thường được biết dưới tên mạng lưới tín nhiệm dựa trên các mối quan hệ ngang hàng (khác với hệ thống X.509 với cấu trúc cây dựa vào các nhà cung cấp chứng thực số). Các phiên bản PGP về sau dựa trên các kiến trúc tương tự như hạ tầng khóa công khai.

PGP sử dụng thuật toán mật mã hóa khóa bất đối xứng. Trong các hệ thống này, người sử dụng đầu tiên phải có một cặp khóa: khóa công khai và khóa bí mật. Người gửi sử dụng khóa công khai của người nhận để mã hóa một khóa chung (còn gọi là khóa phiên) dùng trong các thuật toán mật mã hóa khóa đối xứng. Khóa phiên này chính là khóa để mật mã hóa các thông tin được gửi qua lại trong phiên giao dịch. Rất nhiều khóa công khai của những người sử dụng PGP được lưu trữ trên các máy chủ khóa PGP trên khắp thế giới (các máy chủ mirror lẫn nhau).

Người nhận trong hệ thống PGP sử dụng khóa phiên để giải mã các gói tin. Khóa phiên này cũng được gửi kèm với thông điệp nhưng được mật mã hóa bằng hệ thống mật mã bất đối xứng và có thể tự giải mã với khóa bí mật của người nhận. Hệ thống phải sử dụng cả hai dạng thuật toán để tận dụng ưu thế của cả hai: thuật toán bất đối xứng đơn giản việc phân phối khóa còn thuật toán đối xứng có ưu thế về tốc độ (nhanh hơn cỡ 1000 lần).

Một chiến lược tương tự cũng được dùng (mặc định) để phát hiện xem thông điệp có bị thay đổi hoặc giả mạo người gửi. Để thực hiện 2 mục tiêu trên người gửi phải ký văn bản với thuật toán RSA hoặc DSA. Đầu tiên, PGP tính giá trị hàm băm của văn bản đó rồi tạo ra chữ ký số với khóa bí mật của người gửi và gửi cả văn bản và chữ ký số đến người nhận. Khi nhận được văn bản, người nhận tính lại giá trị băm của văn bản đó đồng thời giải mã chữ ký số bằng khóa công khai của người gửi. Nếu 2 giá trị băm này giống nhau thì có thể khẳng định (với xác suất rất cao) là văn bản chưa bị thay đổi kể từ khi gửi và người gửi đúng là người sở hữu khóa bí mật tương ứng.

Trong quá trình mã hóa cũng như kiểm tra chữ ký, một điều vô cùng quan trọng là khóa công khai được sử dụng thực sự thuộc về người được cho là sở hữu nó. Nếu chỉ đơn giản là download một khóa công khai từ đâu đó sẽ không thể đảm bảo được điều này. PGP thực hiện việc phân phối khóa thông qua chứng thực số được tạo nên bởi những kỹ thuật mật mã sáo cho việc sửa đổi (không hợp pháp) có thể dễ dàng bị phát hiện. Tuy nhiên chỉ điều này thôi thì chưa đủ vì nó chỉ ngăn chặn được việc sửa đổi sau khi chứng thực đã được tạo ra. Người dùng còn cần phải được trang bị khả năng kiểm tra xem khóa công khai có thực sự thuộc về người được cho là sở hữu hay không. Từ phiên bản đầu tiên, PGP đã có một cơ chế hỗ trợ điều này gọi là mạng lưới tín nhiệm. Mỗi khóa công khai (rộng hơn là các thông tin gắn với một khóa hay một người) đều có thể được một bên thứ 3 xác nhận (theo cách điện tử).

Trong các đặc tả gần đây của OpenPGP, các chữ ký tin cậy có thể được sử dụng để tạo ra các nhà cung cấp chứng thực số (CA). Một chữ ký tin cậy có thể chứng tỏ rằng một khóa thực sự thuộc về một người sử dụng và người đó đáng tin cậy để ký xác nhận một khóa của mức thấp hơn. Một chữ ký có mức 0 tương đương với chữ ký trong mô hình mạng lưới tín nhiệm. Chữ ký ở mức 1 tương đương với chữ ký của một CA vì nó có khả năng xác nhận cho một số lượng không hạn chế chữ ký ở mức 0. Chữ ký ở mức 2 tương tự như chữ ký trong danh sách các CA mặc định trong Internet Explorer; nó cho phép người chủ tạo ra các CA khác.

PGP cũng được thiết kế với khả năng hủy bỏ/thu hồi các chứng thực có khả năng đã bị vô hiệu hóa. Về một khía cạnh nào đó, điều này tương đương với danh sách chứng thực bị thu hồi của mô hình hạ tầng khóa công khai. Các phiên bản PGP gần đây cũng hỗ trợ tính năng hạn sử dụng của chứng thực.

Vấn đề xác định mối quan hệ giữa khóa công khai và người sở hữu không phải là vấn đề riêng của PGP. Tất cả các hệ thống sử dụng cặp khóa công khai và khóa bí mật đều phải đối phó với vấn đề này và cho đến nay chưa có một giải pháp hoàn thiện nào được tìm ra. Mô hình ban đầu của PGP trao cho quyền quyết định cuối cùng người sử dụng còn các mô hình PKI thì quy định tất cả các chứng thực phải được xác nhận (có thể không trực tiếp) bởi một nhà cung cấp chứng thực trung tâm.